package com.example.algorithm.sort;

// 学习顺序：第一
// 第i个元素与第 i+1个元素俩俩相比然后互换位置，第一次循环会把最大的元素挪到最后，第二次是把第二大的元素挪到倒数第二...
// 每次都会把最大的元素不断往后冒，大的往后冒泡，才叫冒泡排序。与选择排序刚好相反。复杂度：n^2

// 简单解释一下复杂度。复杂度，可以简单地理解为需要操作的次数。并且，复杂图它只是大致地表示次数的级别，比如说常数级别、对数级别、对数乘以n级别、线性级别n、指数级别等。
// 其中，n^2就是表示是n*n,也就是说是这表示的是次数。从两层for循环来看，虽然不是完全的每层都是n次循环，但是，大致来看的话，它还是属于指数级别的次数的。所以，可以认为，这种两层循环有没有做任何优化的算法，基本都是n^2这种指数级别。

// 冒泡排序和选择排序的时间复杂度都是 O(n^2)。注意，我们这里说的复杂度是指代时间复杂度哦，一般来说，就是和循环的次数挂钩的。
public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {5, 3, 8, 4, 2};

        System.out.println("排序前的数组：");
        printArray(array);

        bubbleSort(array);

        System.out.println("\n排序后的数组：");
        printArray(array);
    }

    // 冒泡排序方法
    // 其实这个很好立即，在脑海中有个理解的概念了之后，写的细节直接靠多写几次就能记忆清楚了。
    public static void bubbleSort(int[] array) {
        int n = array.length;
        // 两层循环。i<n-1,是因为，i是从0开始
        for (int i = 0; i < n - 1; i++) { // 两层循环，i这个循环，仅仅是为了给j那层循环确定上限。所以，j的循环上限，第一次是4，第二次是3，第三次是2...分别对应地是循环5个元素，4个元素，3个元素...
            // j也是从0开始的。j < n-1-i是啥意思呢，n-1是数组长度。i等于0时，j=4，i=1时，j=3，就是和剩下没有排好序的比较呗
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) { // 注意，我们比较仅仅是针对j这个下标进行比较哦。对于i为下标我们不比较。
                    // 交换array[j]和array[j+1]。下面三句仅仅是为了两个元素相互交换位置哦。
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    // 打印数组方法
    public static void printArray(int[] array) {
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
}

// 后记：
// 这种冒泡排序采用的是两两比较，然后立即交换的方式。但是我个人感觉这种方式的话，交换的次数可能还是比较多。它没有引入额外的一个擂台，作为第三方，来流动式地存多次两两比较的那个优胜者。
// 我个人觉得，如果额外的引进一个临时的largest变量，每次比较之后，就仅仅只把值更大的的那个元素的索引记录在largest变量。然后，5个元素比较完之后，这时候已经找出了5个元素里面的最大值。然后把这个最大值固定和无序区的最后一个元素交换。无序区的最后一个元素，也就是，j值值域的上限，也就是n - i - 2。其实我的这种写法的思维，已经在选择排序里面实现了。

